Pilot staffing and training is one of the most complex and costly problems facing the major airlines. If not managed effectively, an airline cannot survive, not to mention profit, in the competitive air transportation market.
By way of example, Continental Airlines provides both domestic and international service to more than 100 destinations around the world. They operate 325 aircraft of nine different fleet types flying 1400 daily flights. Their 5000 pilots are stationed at three domestic and two international crew bases. At least twice a year, Continental conducts a system bid award. These awards provide an opportunity for pilots to use their seniority to increase their pay and improve their work schedules by changing their position (base, fleet, and seat), and provide a way for the airline to adjust staffing levels in response to retirements, attrition, and changes in their business plan. In an average system bid award, 15-20% of the airline's pilots receive new positions.
Prior to the deployment of the invention as described and claimed herein, Continental manpower planners with expert knowledge took more than two weeks to manually generate a single, partial, sub-optimal transition plan based on ensuring adequate staffing levels with no detailed consideration of costs. This manual solution did not include a training schedule. Planners would build the training schedule month by month using pen and paper to implement a training plan.
There is a wide variety of prior art which discloses both manual and computational solution methods for overcoming simple scheduling problems. None of the known prior art compares to this invention in scope or complexity. Some prior art, however, serves as basic building blocks for this invention. For example, branch and bound techniques are powerful tools used by operations research practitioners to solve difficult combinatorial problems. For a detailed description of branch and bound techniques, see pp. 515-526 of Introduction to Operations Research, by Frederick S. Hillier and Gerald J. Lieberman, McGraw-Hill, Inc., N.Y., 1995. The discussion includes an introductory example with a graphic illustrating a branch and bound tree. See also “Class Scheduling for Pilot Training” by Xiangtong Qi, Jonathan Bard, and Gang Yu, submitted for publication to Operations Research, June 2001, in which one of the inventors of the current invention disclosed part of the current invention, and the co-authors of the article provided a good overview of similar but not directly applicable prior art. In addition, “Scheduling Pilot Training”, by Mikael Rittri and Goran Allerbo of Carmenta AB, presented at ILOG International Users Meeting, October 2000, describes a different solution strategy without mixed integer programming models or use of branch and bound techniques, and which fails to address contractual rules such as days off rules, and requirements for recurrent training.
The invention described and claimed herein has been developed as part of an integrated decision support system by CALEB Technologies Corp. of Austin, Tex., to face the training scheduling challenge. More particularly, the invention is required to schedule hundreds of pilots simultaneously for multiple different types of curriculum over a planning horizon of up to one year. Each training class has a variable start date, and the training schedules which are generated must conform to complex contractual and operational constraints. Schedules cannot be generated weekly or monthly and then repeated, due to the varying requirements for training over time. The invention minimizes pilot time spent in training, while maximizing training resource utilization. Large volumes of data are managed and state-of-the-art optimization modeling and solution techniques are employed to efficiently allocate human and training resources, and attain optimal operational and financial performance. The invention has recently been deployed at Continental Airlines, and has demonstrated remarkable savings with a positive effect on Continental's operations.
In response to a system bid award, the airline builds a transition plan that establishes the timing and number of pilot hires, training assignments, advancements, and releases. Based upon the above information, the invention builds a training schedule detailing all training events for each student and training resource.
By using the invention, a complete, optimized solution is obtained rapidly that includes a training schedule which complements the transition plan for the entire planning horizon. In the execution of the solution process, classes are addressed one at a time, then two at a time, then three at a time, and so forth as long as time allotted to the solution process remains. Thus, step by step refinement of the training schedule occurs until either all classes are handled at the same time or no time remains for the solution process. When the solution process has progressed to all classes being handled at the same time, a complete optimized solution is said to have been generated. The primary objective of the training schedule is to minimize the number of pilot days required to teach a fixed curriculum for each pilot with limited training resources. The training schedule which is produced by the invention is constrained by physical limits of the training resources, and contractual limitations imposed by the pilot's contract with the airline. The planning horizon during which training is to occur is variable, but is generally 12 months in duration. By using the invention to create training schedules, certain benefits are realized including training cost savings from better utilization of expensive resources, and reduced time for pilots to complete training.
As the training scheduling problem was studied, it was determined that the problem was too large and too complex to solve with a single model or solution method. The invention therefore decomposes the problem into two parts which are used for each fleet. The first part is a unique branch and bound algorithm where branch and bound trees are used to schedule daily activity for all classes. A single branch and bound tree is not used to schedule all of the classes for a fleet because it is too time consuming. A series of branch and bound trees are used progressively, therefore, to schedule subsets of classes until all classes are scheduled. In the second part, a mixed integer programming model is used to refine the solution from the branch and bound algorithm to obtain a detailed hourly assignment of resources to students and to include time for recurrent training.
In accordance with the invention, training schedules for entire airlines may be both generated and optimized rapidly (from seconds to minutes) to produce minimum length training schedules to ensure that all training requirements are met through efficient use of training resources.